package code.c03_stackQueue.application;

/**
 * @author thinkpad - 83start
 * @version v1.0
 * @create 2022/10/2 22:42
 * @package code.c03_stackQueue.application
 * @description 【栈的综合运用】用栈求解简单表达式求值问题
 * 求解简单表达式：
 * 1. 先将表达式 exp 转换成 后缀表达式 postexp
 * 2. 对该后缀表达式求值
 * <p>
 * 后缀表达式求解：
 * 1. 从左到右遍历后缀表达式，若遇到一个运算数，就将他进运算数栈
 * 2. 若遇到一个运算符 op ,就从运算数栈中连续出栈两个运算数
 * 3. 计算 a op b 的值，并将计算结果进运算数栈
 * 4. 对整个后缀表达式遍历结束后，栈顶元素就是计算结果
 */

import javax.print.DocFlavor;
import java.util.Stack;

/**
 * 中缀表达式 转换成 后缀表达式
 */
public class ExpressClass {
    // 中缀表达式
    String exp;
    // 后缀表达式
    String postexp;


    public void setExp(String exp) {
        this.exp = exp;
    }
    public String getPostexp() {
        return postexp;
    }

    /**
     * 中缀表达式 转为 后缀表达式
     */
    public void trans() {
        Stack<Character> opor = new Stack<>();
        int i = 0;
        char ch, e;

        while (i < exp.length()) {
            ch = exp.charAt(i);
            if (ch == '(') {
                opor.push(ch);
            } else if (ch == ')') {
                while (!opor.empty() && opor.peek() != '(') {
                    e = opor.pop();
                    postexp += e;
                }
                opor.pop();
            } else if (ch == '+' || ch == '-') {
                while (!opor.empty() && opor.peek() != '(') {
                    e = opor.pop();
                    postexp += e;
                }
                opor.push(ch);
            } else if (ch == '*' || ch == '/') {
                while (!opor.empty() && opor.peek() != '(') {
                    e = opor.pop();
                    postexp += e;
                }
                opor.push(ch);
            } else {
                while (ch >= '0' && ch <= '9') {
                    postexp += ch;
                    i++;
                    if (i < exp.length()) {
                        ch = exp.charAt(i);
                    } else {
                        break;
                    }
                }
                i--;
                postexp += '#';
            }
            i++;
        }
        while (!opor.empty()) {
            e = opor.pop();
            postexp += e;
        }
    }

    /**
     * 求后缀表达式的值
     * @return
     */
    public double getValue() {
        Stack<Double> opand = new Stack<>();
        double a, b, c, d;
        int i = 0;
        char ch;
        while (i < postexp.length()) {
            ch = postexp.charAt(i);
            switch (ch) {
                case '+': {
                    a = opand.pop();
                    b = opand.pop();
                    c = a + b;
                    opand.push(c);
                    break;
                }
                case '-': {
                    a = opand.pop();
                    b = opand.pop();
                    c = b - a;
                    opand.push(c);
                    break;
                }
                case '*': {
                    a = opand.pop();
                    b = opand.pop();
                    c = b * a;
                    opand.push(c);
                    break;
                }
                case '/': {
                    a = opand.pop();
                    b = opand.pop();
                    if (a != 0) {
                        c = b / a;
                        opand.push(c);
                    } else {
                        throw new ArithmeticException("运算错误：除数为0");
                    }
                    break;
                }
                default: {
                    d = 0;
                    while (ch >= '0' && ch <= '9') {
                        d = 10 * d + (ch - '0');
                        i++;
                        ch = postexp.charAt(i);
                    }
                    opand.push(d);
                    break;
                }
            }
            i++;
        }
        return opand.peek();
    }

    public static void main(String[] args) {
        double v;
        ExpressClass expressClass = new ExpressClass();
        String str= "(60-30)/(4+2)";
        expressClass.setExp(str);

        System.out.println("中缀表达式：" + str);

        expressClass.trans();
        System.out.println("后缀表达式：" + expressClass.getPostexp());

        System.out.println("求值结果：" + expressClass.getValue());

    }
}
